#include <assert.h>
#include "pointer_set.h"

void ptr_set_open_alloced( PTR_SET s, size_t init_cap )
{
    s->sz = 0;
    s->cap = init_cap;
    s->data = calloc( s->cap, sizeof( s->data[0] ) );
}

int ptr_compare( const void *a, const void *b )
{
    return (*((void **)a)) - (*((void **)(b)));
}

bool ptr_set_contains( PTR_SET s, void *ptr )
{
    return !!bsearch( &ptr, s->data, s->sz, sizeof( s->data[0] ), ptr_compare );
}

/* s <= s \/ {ptr} */
void ptr_set_insert( PTR_SET s, void *ptr )
{
    if( !ptr_set_contains( s, ptr ) )
    {
        assert( s->sz <= s->cap );
        if( s->sz == s->cap )
        {
            s->cap *= 2;
            s->data = realloc( s->data, s->cap * sizeof( s->data[0] ) );
        }
        s->data[ s->sz ] = ptr;
        ++s->sz;
        mergesort( s->data, s->sz, sizeof( s->data[0] ), ptr_compare );
    }
}

/* s <= s - {ptr} */
void ptr_set_subtract( PTR_SET s, void *ptr )
{
    void **elem = bsearch( &ptr, s->data, s->sz, sizeof( s->data[0] ), ptr_compare );
    if( elem )
    {
        while( 1 + elem - s->data < s->sz )
        {
            elem[0] = elem[1];
            ++elem;
        }
        --s->sz;
    }
}

/* s1 <= s1 - s2 */
void ptr_set_diff( PTR_SET s1, PTR_SET s2 )
{
    size_t i;
    for( i = 0; i < s2->sz; ++i )
    {
        ptr_set_subtract( s1, s2->data[i] );
    }
}

/* s1 <= s1 \/ s2 */
void ptr_set_union( PTR_SET s1, PTR_SET s2 )
{
    size_t i;
    for( i = 0; i < s2->sz; ++i )
    {
        ptr_set_insert( s1, s2->data[i] );
    }
}

/* s1 <= s1 /\ s2 */
void ptr_set_intersect( PTR_SET s1, PTR_SET s2 )
{
    size_t read1 = 0, write1 = 0, idx2 = 0, sz1 = s1->sz;
    while( read1 < sz1 && idx2 < s2->sz )
    {
        if( s1->data[ read1 ] < s2->data[ idx2 ] )
            ++read1;
        else if( s1->data[ read1 ] > s2->data[ idx2 ] )
            ++idx2;
        else
        {
            /* The interesting case */
            if( read1 > write1 )
                s1->data[ write1 ] = s1->data[ read1 ];
            ++read1;
            ++write1;
            ++idx2;
        }
    }
    s1->sz = write1;
}

/* end pointer set "library" */
